package pkg0;


import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Alogorithm_LRU
{
	public static void main(String[] args)
	{
		int[] memoryRequest = new int[]{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
		int l = lru2(memoryRequest, 3);
		int total = memoryRequest.length;
		System.out.println("Page lake " + l + " time(s) with total " + total + ", page lake rate is " + (float)l * 100 / total  + "%");
	}
	
	public static int lru(int[] memoryRequest, int stackSize) {
		int pageLakeCount = 0;
		if(stackSize > 0) {
			Stack<Integer> stack = new Stack<Integer>();
			int memoryRequestLen = memoryRequest.length;
			for(int i = 0; i < memoryRequestLen; i++) {
				// find mem data into stack
				boolean isHit = false;
				for(Integer integer : stack) {
					if(integer.intValue() == memoryRequest[i]) {
						isHit = true;
						break;
					}
				}
				if(isHit) {
					// hitted 
					System.out.println(memoryRequest[i] + "\n\t[OK] " + stack.toString());
					continue ;
				} else {
					pageLakeCount ++;
					// lru core : search forwwrd, and select lnru data.
					// 1. when stack is not full
					if(stack.size() < stackSize) {
						stack.push(Integer.valueOf(memoryRequest[i]));
					} else {
						boolean[] flag = new boolean[stackSize];
						int n = stackSize;
						for(int j = i - 1; j >= 0 && n > 1; j --) {
							for(int x = 0; x < flag.length; x ++) {
								if(flag[x] == false && memoryRequest[j] == stack.get(x).intValue()) {
									flag[x] = true;
									n --;
								}
							}
						}
						for(int u = 0; u < flag.length; u ++) {
							if(flag[u] == false) {
								stack.set(u, Integer.valueOf(memoryRequest[i]));
								break;
							}
						}
					}
					System.out.println(memoryRequest[i] + "\n\t" + stack.toString());
				}
				
			}
		} 
		return pageLakeCount;
	}
	
	public static int lru2(int[] memoryRequest, int stackSize) {
		int pageLakeCount = 0;
		
		if(stackSize > 0) {
			Stack<Integer> stack = new Stack<Integer>();
			List<Integer> queue = new LinkedList<Integer>();
			int memoryRequestLen = memoryRequest.length;
			for(int i = 0; i < memoryRequestLen; i++) {
				// find mem data into stack
				boolean isHit = false;
				for(Integer integer : stack) {
					if(integer.intValue() == memoryRequest[i]) {
						isHit = true;
						break;
					}
				}
				if(isHit) {
					// hitted 
					for(int d = 0; d < queue.size(); d ++) {
						if(queue.get(d).intValue() == memoryRequest[i]) {
							queue.add(queue.remove(d));
						}
					}
					System.out.println(memoryRequest[i] + "\n\t[OK] " + stack.toString());
					continue ;
				} else {
					pageLakeCount ++;
					// lru core : search forwwrd, and select lnru data.
					// 1. when stack is not full
					if(stack.size() < stackSize) {
						stack.push(Integer.valueOf(memoryRequest[i]));
						queue.add(Integer.valueOf(memoryRequest[i]));
					} else {
						Integer in = queue.remove(0);
						for(int j = 0; j < stack.size(); j ++) {
							if(stack.get(j).intValue() == in.intValue()) {
								stack.set(j, Integer.valueOf(memoryRequest[i]));
								queue.add(Integer.valueOf(memoryRequest[i]));
								break;
							}
						}
					}
					System.out.println(memoryRequest[i] + "\n\t" + stack.toString());
				}
				
			}
		} 
		return pageLakeCount;
	}
};

